package 中等.其他;

import java.util.*;

/**
 * 力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，
 * 安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工
 * 卡的次数大于等于三次，这个系统会自动发布一个 警告 。
 * 给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应
 * 一个人的名字和他在 某一天 内使用员工卡的时间。
 * 使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。
 * 请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。
 * 请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "23:51" - "00:10" 
 * 不被视为一小时内，因为系统记录的是某一天内的使用情况。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period
 */
public class 警告一小时内使用相同员工卡大于等于三次的人_1604 {

    public static void main(String[] args) {

        System.out.println(alertNames2(new String[]{"a", "a", "a", "a", "a", "b", "b", "b", "b", "b", "b"},
                new String[]{"23:20", "11:09", "23:30", "23:02", "15:28", "22:57", "23:40", "03:43", "21:55", "20:38", "00:19"}));

        //["a","a","a","a","a","b","b","b","b","b","b"]
        //["23:20","11:09","23:30","23:02","15:28","22:57","23:40","03:43","21:55","20:38","00:19"]

        System.out.println(getMinutes("19:49") - getMinutes("18:51"));

    }

    /**
     * 滑动窗口+数组缓存排序
     * 1，窗口里面最多时间间隔为 60 分钟
     * 2，建立一个临时数组，将每个人的时间从小到大排序
     */
    public static List<String> alertNames(String[] keyName, String[] keyTime) {
        Set<String> set = new HashSet<>();

        String[][] temp = new String[keyName.length][2];
        for (int i = 0; i < keyName.length; i++) {
            temp[i] = new String[]{keyName[i], keyTime[i]};
        }
        Arrays.sort(temp, (a, b) -> {
            if (a[0].equals(b[0])) {
                return getMinutes(a[1]) - getMinutes(b[1]);
            } else {
                return a[0].compareTo(b[0]);
            }
        });

        int left = 0;
        while (left < keyTime.length) {
            int right = left + 1;
            while (right < keyName.length &&
                    temp[right][0].equals(temp[left][0]) &&
                    getMinutes(temp[right][1]) - getMinutes(temp[left][1]) <= 60 &&
                    getMinutes(temp[right][1]) - getMinutes(temp[left][1]) > 0) {
                right++;
            }

            if (right - left >= 3 &&
                    getMinutes(temp[right - 1][1]) - getMinutes(temp[left][1]) <= 60) {
                set.add(temp[left][0]);
            }

            if (right < keyTime.length &&
                    getMinutes(temp[right][1]) - getMinutes(temp[left][1]) <= 60) {
                left = right;
            } else {
                left++;
            }
        }

        List<String> list = new ArrayList<>(set);
        list.sort((a, b) -> a.compareTo(b));
        return list;
    }

    private static int getMinutes(String date) {
        String[] split = date.split(":");
        return Integer.valueOf(split[0]) * 60 + Integer.valueOf(split[1]);
    }

    /**
     * 滑动窗口+哈希表缓存排序
     * 1，将每个人对应的使用记录放入哈希表中，每个人自己进行排序，而不是总体排序
     * 2，时间排序可以直接用 字典序 进行比较大小
     */
    public static List<String> alertNames2(String[] keyName, String[] keyTime) {
        List<String> list = new ArrayList<>();

        // 时间转成分钟数进行存储
        Map<String, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < keyName.length; i++) {
            map.putIfAbsent(keyName[i], new ArrayList<>());
            List<Integer> curList = map.get(keyName[i]);

            int minutes = (keyTime[i].charAt(0) - '0') * 10 * 60 +
                    (keyTime[i].charAt(1) - '0') * 60 +
                    (keyTime[i].charAt(3) - '0') * 10 +
                    keyTime[i].charAt(4) - '0';
            curList.add(minutes);
        }

        for (Map.Entry<String, List<Integer>> entry : map.entrySet()) {
            List<Integer> curList = entry.getValue();
            curList.sort((a, b) -> a - b);
            // 判断每个相邻的三个时间 [i-2,i]，时间间隔是否<=60分钟
            for (int i = 2; i < curList.size(); i++) {
                if (curList.get(i) - curList.get(i - 2) <= 60) {
                    list.add(entry.getKey());
                    break;
                }
            }
        }

        list.sort((a, b) -> a.compareTo(b));
        return list;
    }

}
